SQLite在存储在外部的数据库是以B-Tree来组织的。关于B-tree的细节，参考
IT之家IT之家
IT之家IT之家 Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
IT之家IT之家 "Sorting And Searching", pages 473-480. Addison-Wesley
IT之家IT之家 Publishing Company, Reading, Massachusetts.
IT之家IT之家
基本思想是文件包含的每一页都包括N个数据库入口和N+1个指向子页的指针。文件分成很多页存储。为什么这么干，因为内存分页管理机制闹得。外存中每个页就是B树的一个节点。
----------------------------------------------------------------
| Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
----------------------------------------------------------------
Ptr(0)指向的页上的所有的key的值都小于Key(0)。所有Ptr(1)指向的页和子页的所有的key的值都大于Key(0)，小于Key(1)。所有Ptr(N)指向的页和子页的key的值都大于Key(N-1)，等等。

为了知道一个特定的key，需要从磁盘上以O(long(M))来读取，其中M是树的阶数。内存中找不到了，就发生缺页中断。
主要是解决内存中找不到的问题。一方面换出来一些。一方面换进去一些。换进去的时候要找到他们再硬盘的哪个页面上啊。
（B树的优点就是适合于用块儿存储的存储设备上。）利用所以，可以知道他们们在哪个页面上。

在SQLite的实现中，一个文件可以含有1个或的过独立的BTree。每一个BTree由它的根页的索引来标识。所有入口的key和数据组成了有效负荷(payload)。数据库的一页有一个固定的有效负荷总量。如果负荷大于了预先设定的值，那么剩余的字节就会被存储在溢出页上。一个入口的有效负荷再加上前向指针（the preceding pointer）构成了一格(cell)。每一页都有一个小头部，包含了Ptr(N)指针和其它一些信息，例如key和数据的大小。

格式细节
一个文件分成了多个页。第一页叫做页1，第二页叫做页2，一次类推。页的个数为0表示没有页。页的大小可以从512 到 65536。每一页或者是一个btree页，或者是一个freelist页，或者是一个溢出页。
第一页一定是一个btree页。第一页的前面100个字节包含了一个特殊的首部(文件头)，它是这个文件的描述。
文件头的个数如下：
IT之家IT之家 OFFSET SIZE DESCRIPTION
IT之家IT之家 0 16 Header string（首部字符串）: "SQLite format 3\000"
IT之家IT之家 16 2 Page size in bytes（页的字节数）.
IT之家IT之家 18 1 File format write version（文件写操作的版本）
IT之家IT之家 19 1 File format read version （文件读操作的版本）
IT之家IT之家 20 1 Bytes of unused space at the end of each page（每一页结尾未使用的字节）
IT之家IT之家 21 1 Max embedded payload fraction（最大的嵌入有效负荷分片）
IT之家IT之家 22 1 Min embedded payload fraction（最小的嵌入有效负荷分片）
IT之家IT之家 23 1 Min leaf payload fraction（最小的页有效负荷分片）
IT之家IT之家 24 4 File change counter （文件变化计数器）
IT之家IT之家 28 4 Reserved for future use （保留字节）
IT之家IT之家 32 4 First freelist page （第一个freelist页）
IT之家IT之家 36 4 Number of freelist pages in the file （本文件中freelist页的个数）
IT之家IT之家 40 60 15 4-byte meta values passed to higher layers（）
IT之家IT之家
所有的整数都是大端的。

每次修改文件时，文件变化计数器都会增加。这个计数器可以让其他进程知道何时文件被修改了，他们的cache是否需要清理。

最大嵌入有效负荷分片是一页的所有可用空间，被标准B-tree（非叶数据）表的单独的一个所能使用的总量。值255代表100%。默认情况下，一格(cell)的最大量被限制为，至少有4格才能填满一页。因此，默认的最大嵌入负荷分片是64。

如果一页的有效负荷大于了最大有效负荷，那么剩下的数据就要被存储到溢出页。一旦分配了一个溢出页，有可能会有许多数据也被转移到这个溢出页，但是不会让格cell的大小小于最小嵌入有效负荷分片的。

最小页有效负荷分片与最小嵌入有效负荷分片类似，但是它是应用于LEAFDATA tree中的叶节点。一个LEAFDATA的最大有效负荷分片为100%（或者是值255），它不用再首部指定。

BTree的每一页被分为三部分：首部，格（cell）指针数组，和格cell的内容。页1还会在页首部有100字节的文件头。
IT之家IT之家
IT之家IT之家 |----------------|
IT之家IT之家 | file header | 100 bytes. Page 1 only.
IT之家IT之家 |----------------|
IT之家IT之家 | page header | 8 bytes for leaves. 12 bytes for interior nodes
IT之家IT之家 |----------------|
IT之家IT之家 | cell pointer | | 2 bytes per cell. Sorted order.
IT之家IT之家 | array | | Grows downward
IT之家IT之家 | | v
IT之家IT之家 |----------------|
IT之家IT之家 | unallocated |
IT之家IT之家 | space |
IT之家IT之家 |----------------| ^ Grows upwards
IT之家IT之家 | cell content | | Arbitrary order interspersed with freeblocks.
IT之家IT之家 | area | | and free space fragments.
IT之家IT之家 |----------------|
IT之家IT之家
页首部如下图所示：
IT之家IT之家
IT之家IT之家 OFFSET SIZE DESCRIPTION
IT之家IT之家 0 1 Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
IT之家IT之家 1 2 byte offset to the first freeblock
IT之家IT之家 3 2 number of cells on this page
IT之家IT之家 5 2 first byte of the cell content area
IT之家IT之家 7 1 number of fragmented free bytes
IT之家IT之家 8 4 Right child (the Ptr(N) value). Omitted on leaves.
IT之家IT之家
标志位定义了这个BTree页的格式。叶leaf标志意味着这一页没有孩子children。zerodata0数据表示这一页只含有key，没有数据；intkey标志意味着key是一个整数，而且是被存储在格cell首部的key大小处，而不是在有效负荷区域。

格cell指针数组从页首部开始。格cell指针数组包含0个或多余2个字节的数字，这个数字代表格cell内容区域中的格cell内容从文件起始位置的偏移量。格cell指针式有序的。系统尽力保证空闲空间位于最后一个格cell指针之后，这样可以保证新的格cell可以很快的添加，而不用重新整理（defragment）这一页。

格cell内容存储在页的末尾，且是向文件的起始方向增长。

在格cell内容区域中的未使用的空间被收集到链表freeblocks上。每一个freeblock至少有4个字节。第一个freeblock的偏移在页首部给出了。Freeblock是增序的。因为一个freeblock至少有4个字节，所有在格cell内容区域的3个或是哦啊与3个的未用空间不能存在于freeblock链表上。这些3个或少于3个的空闲空间被称为碎片。所有碎片的总个数被记录下来，存储于页首部的偏移7的位置。

IT之家IT之家 SIZE DESCRIPTION
IT之家IT之家 2 Byte offset of the next freeblock
IT之家IT之家 2 Bytes in this freeblock
IT之家IT之家

格cell是可变长度的。格cell被存储于页的末尾格cell内容区域。指向格cell的cell指针数组紧跟在页首部的后面。格cell不必是连续或者有序的，但是格cell指针是连续和有序的。

格cell内容充分利用了可变长度整数。可变长度整数是从1到9个字节，每个字节的低7位被使用。整个整数由8位的字节组成，其中第一个字节的第8位被清零。整数最重要的字节出现在第一个。可变长度整数一般不多于9个字节。作为一种特殊情况，第九个字节的所有8个字节都会被认为是数据。这就允许了64位整数变编码为9个字节。
IT之家IT之家 0x00 becomes 0x00000000
IT之家IT之家 0x7f becomes 0x0000007f
IT之家IT之家 0x81 0x00 becomes 0x00000080
IT之家IT之家 0x82 0x00 becomes 0x00000100
IT之家IT之家 0x80 0x7f becomes 0x0000007f
IT之家IT之家 0x8a 0x91 0xd1 0xac 0x78 becomes 0x12345678
IT之家IT之家 0x81 0x81 0x81 0x81 0x01 becomes 0x10204081
本篇文章来源于 Linux公社网站() 原文链接：